package myLInkedList;

public class MyLinkedList {

    static class Node{
        int val;
        Node prev;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }

    Node head;//定位头结点
    Node last;//定位尾节点

    //add方法默认是尾插法
    public void add(int val) {
        addLast(val);
    }

    //头插法
    public void addFirst(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            last = newNode;
            return;
        }
        head.prev = newNode;
        newNode.next = head;
        head = newNode;
    }

    //尾插法
    public void addLast(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            last = newNode;
            return;
        }
        last.next = newNode;
        newNode.prev = last;
        last = newNode;
    }

    //指定下标插入结点，下标从0开始
    public void insert(int index, int val) {
        if (indexIsLigal(index)) {  //如果不合法
            throw new MyLinkedListException("根据下标插入结点时，下标不合法！");
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }
        Node cur = searchByIndex(index);//指定下标节点
        Node newNode = new Node(val);
        cur.prev.next = newNode;
        newNode.next = cur;
        newNode.prev = cur.prev;
        cur.prev = newNode;
    }

    //返回指定下标节点的引用
    public Node searchByIndex(int index) {
        Node tmp = head;
        while (index > 0) {
            tmp = tmp.next;
            index--;
        }
        return tmp;
    }

    //检查下标的合法性,合法就返回false
    private boolean indexIsLigal(int index) {
        return index < 0 || index > size();
    }

    public int size() {
        int count = 0;
        Node tmp = head;
        while (tmp != null) {
            tmp = tmp.next;
            count++;
        }
        return count;
    }

    public void display() {
        Node tmp = head;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    //删除第一个值为val的节点
    public void remove(int key) {
        Node tmp = head;
        if (head.val == key) {
            head = head.next;
            if (head != null) {  //防止元素只有一个
                head.prev = null;
            }
            return;
        }
        tmp = head.next; //头结点已经判断过了。直接往下跳一个

        while (tmp != last) {
            if (tmp.val == key) {
                tmp.prev.next = tmp.next;
                tmp.next.prev = tmp.prev;
                return;
            }
            tmp = tmp.next;
        }
        if (last.val == key) {
            last = last.prev;
            if (last != null) {
                last.next = null;
            }
            return;
        }
        System.out.println("链表中不含拥有此数值的节点");
    }

    //是否含有
    public boolean contains(int key) {
        Node tmp = head;
        while (tmp != null) {
            if (tmp.val == key) {
                return true;
            }
        }
        return false;
    }
}
